package class31To40;


import java.util.ArrayList;

// https://leetcode.cn/problems/basic-calculator-iii/
public class BasicCalculatorIII {

    public static int where;

    public static int calculate(String str) {
        where = 0;
        return f(str.toCharArray(), 0);
    }

    private static int f(char[] s, int i) {
        int cur = 0;
        ArrayList<Integer> numbers = new ArrayList<>();
        ArrayList<Character> options = new ArrayList<>();
        while (i < s.length && s[i] != ')') {
            if (s[i] >= '0' && s[i] <= '9') {
                cur = cur * 10 + s[i++] - '0';
            } else if (s[i] != '(') {
                push(numbers, options, cur, s[i++]);
                cur = 0;
            } else {
                cur = f(s, i + 1);
                i = where + 1;
            }
        }
        push(numbers, options, cur, '+');
        where = i;
        return calc(numbers, options);

    }

    private static int calc(ArrayList<Integer> numbers, ArrayList<Character> options) {
        int n = numbers.size();
        int ans = numbers.get(0);
        for (int i = 1; i < n; i++) {
            char op = options.get(i - 1);
            ans += op == '+' ? numbers.get(i) : -numbers.get(i);
        }
        return ans;
    }

    private static void push(ArrayList<Integer> numbers, ArrayList<Character> options, int cur, char op) {
        int n = numbers.size();
        if (n == 0 || options.get(n - 1) == '+' || options.get(n - 1) == '-') {
            numbers.add(cur);
            options.add(op);
        } else {
            int topNum = numbers.get(n - 1);
            char topOp = options.get(n - 1);
            if (topOp == '*') {
                numbers.set(n - 1, topNum * cur);
            }
            if (topOp == '/') {
                numbers.set(n - 1, topNum / cur);
            }
            options.set(n - 1, op);
        }
    }
}
